package net.xuele.learn.leetcode.hot100;

import net.xuele.learn.leetcode.ListNode;
import org.junit.Test;

import java.util.*;

/**
 * @Author: yubo
 * @date: 11:59 2020/4/27
 * @Description: 类描述
 */

public class Solution {

    /**
     * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
     * <p>
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
     * <p>
     *  
     * <p>
     * 示例:
     * <p>
     * 给定 nums = [2, 7, 11, 15], target = 9
     * <p>
     * 因为 nums[0] + nums[1] = 2 + 7 = 9
     * 所以返回 [0, 1]
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/two-sum
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {

        int[] result = new int[2];
        Map<Integer, Integer> hash = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (hash.containsKey(nums[i])) {
                result[0] = i;
                result[1] = hash.get(nums[i]);
                return result;
            }
            // 将数据存入 key为补数 ，value为下标
            hash.put(target - nums[i], i);
        }

        return result;

    }

    /**
     * 给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
     * <p>
     * 函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
     * <p>
     * 说明:
     * <p>
     * 返回的下标值（index1 和 index2）不是从零开始的。
     * 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
     * 示例:
     * <p>
     * 输入: numbers = [2, 7, 11, 15], target = 9
     * 输出: [1,2]
     * 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param nums
     * @param target
     * @return 有序数组！！！！
     */
    public int[] wtwoSumOrderly(int[] nums, int target) {
        if (nums == null) return null;
        int i = 0, j = nums.length - 1;
        while (i < j) {
            int result = nums[i] + nums[j];
            if (result == target) {
                return new int[]{i + 1, j + 1};
            } else if (result < target) {
                i++;
            } else {
                j--;
            }
        }
        return null;
    }


    /**
     * 给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。
     * <p>
     * 示例1:
     * <p>
     * 输入: 5
     * 输出: True
     * 解释: 1 * 1 + 2 * 2 = 5
     *  
     * <p>
     * 示例2:
     * <p>
     * 输入: 3
     * 输出: False
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/sum-of-square-numbers
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * <p>
     * 本题的关键是右指针的初始化，实现剪枝，从而降低时间复杂度。设右指针为 x，
     * 左指针固定为 0，为了使 02 + x2 的值尽可能接近 target，我们可以将 x 取为 sqrt(target)
     * <p>
     * 右指针最大的可取值为Math.sqrt(c)！！！
     */
    public boolean judgeSquareSum(int c) {
        if (c < 0) return false;
        int i = 0, j = (int) Math.sqrt(c);
        while (i <= j) {
            int result = i * i + j * j;
            if (result == c) {
                return true;
            } else if (result < c) {
                i++;
            } else {
                j--;
            }
        }
        return false;
    }


    /**
     * 编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
     * <p>
     * 示例 1:
     * <p>
     * 输入: "hello"
     * 输出: "holle"
     * 示例 2:
     * <p>
     * 输入: "leetcode"
     * 输出: "leotcede"
     * 说明:
     * 元音字母不包含字母"y"。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/reverse-vowels-of-a-string
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param s
     * @return
     */
    private final static HashSet<Character> vowels = new HashSet<>(
            Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));

    public String reverseVowels(String s) {
        if (s == null) return null;
        int i = 0, j = s.length() - 1;
        char[] result = new char[s.length()];
        while (i <= j) {
            char ci = s.charAt(i);
            char cj = s.charAt(j);
            // 不是元音直接添加进char数据即可，并且指针需要加1
            if (!vowels.contains(ci)) {
                result[i++] = ci;
            } else if (!vowels.contains(cj)) {
                // 不是元音直接添加进char数据即可，并且指针需要减1
                result[j--] = cj;
            } else {
                // 二者都是元音，需要交换位置，并且指针需要进行相关的操作
                result[i++] = cj;
                result[j--] = ci;
            }
        }
        return new String(result);
    }


    /**
     * 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
     * <p>
     *  
     * <p>
     * 说明:
     * <p>
     * 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
     * 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
     *  
     * <p>
     * 示例:
     * <p>
     * 输入:
     * nums1 = [1,2,3,0,0,0], m = 3
     * nums2 = [2,5,6],       n = 3
     * <p>
     * 输出: [1,2,2,3,5,6]
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/merge-sorted-array
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n     解题思路：
     *              1、新数组的大小是二者大小之和
     *              2、原先的两个数组都是有序的
     *              3、从后面往前遍历，为什么呢？因为新生成的数组是在nums1上的，从前遍历，会导致部分元素被覆盖
     *              <p>
     *              极致做法：
     *              nums2的元素全部扔到nums1中，然后再排序
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index1 = m - 1, index2 = n - 1;
        int indexMerge = m + n - 1;
        while (index1 >= 0 || index2 >= 0) {
            if (index1 < 0) {
                // 数组1上没有元素
                nums1[indexMerge--] = nums2[index2--];
            } else if (index2 < 0) {
                // 数组2上没元素
                nums1[indexMerge--] = nums1[index1--];
            } else if (nums1[index1] > nums2[index2]) {
                // 数组1的最后一个元素大于数组2的最后一个元素，那么归并后的数据的最后一元素为数组1的
                // 此时数组1索引减1，数组2的索引不变
                nums1[indexMerge--] = nums1[index1--];
            } else {
                // 数组2的个元素大于数组1的
                nums1[indexMerge--] = nums2[index2--];
            }
        }
    }


    /**
     * 给定一个链表，判断链表中是否有环。
     * <p>
     * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/linked-list-cycle
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param head
     * @return 链表有环，快慢指针重合！！！
     * <p>
     * 快慢指针，或者hash表
     * <p>
     * <p>
     * Set<ListNode> nodesSeen = new HashSet<>();
     * while (head != null) {
     * if (nodesSeen.contains(head)) {
     * return true;
     * } else {
     * nodesSeen.add(head);
     * }
     * head = head.next;
     * }
     * return false;
     */
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    /**
     * 给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。
     * <p>
     * 示例 1:
     * <p>
     * 输入:
     * s = "abpcplea", d = ["ale","apple","monkey","plea"]
     * <p>
     * 输出:
     * "apple"
     * 示例 2:
     * <p>
     * 输入:
     * s = "abpcplea", d = ["a","b","c"]
     * <p>
     * 输出:
     * "a"
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param s
     * @param d
     * @return 通过删除字符串 s 中的一个字符能得到字符串 t，可以认为 t 是 s 的子序列，也就是说字典中的元素是s的子串
     * 我们可以使用双指针来判断一个字符串是否为另一个字符串的子序列。
     */
    public String findLongestWord(String s, List<String> d) {

        String longestWord = "";

        for (String target : d) {
            int l1 = longestWord.length();
            int l2 = target.length();
            // 需要返回长度最长，并且二者长度想等时，返回字典顺序最小的字符串
            if (l1 > l2 || (l1 == l2 && longestWord.compareTo(target) < 0)) {
                continue;
            }
            if (isSubstr(s, target)) {
                longestWord = target;
            }
        }
        return longestWord;
    }


    private boolean isSubstr(String s, String target) {
        int i = 0, j = 0;
        while (i < s.length() && j < target.length()) {
            if (s.charAt(i) == target.charAt(j)) {
                j++;
            }
            // 模拟删除的过程
            i++;
        }
        // 这一步是在判断s与target中相等的字符数是否于target的长度相等，相等则说明target是s的子序列
        return j == target.length();
    }


    /**
     * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     * <p>
     * 示例 1:
     * <p>
     * 输入: [3,2,1,5,6,4] 和 k = 2
     * 输出: 5
     * 示例 2:
     * <p>
     * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
     * 输出: 4
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param nums
     * @param k
     * @return
     * @answer top k问题，优先队列亦即堆！
     */
    public int findKthLargest(int[] nums, int k) {
        // 构建最小堆
        PriorityQueue<Integer> min = new PriorityQueue<>(Comparator.comparingInt(n -> n));
        for (int i = 0; i < nums.length; i++) {
            min.offer(nums[i]);
            // 保证堆内只有两个元素，堆会为我们自动维持数据的排序！！！
            if (min.size() > k) {
                // 删除最小的元素
                min.poll();
            }
        }
        return min.poll();
    }

    /**
     * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
     * <p>
     * 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
     * <p>
     * 注意：你不能在买入股票前卖出股票。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 0) {
            return 0;
        }
        int soFarMin = prices[0];
        int max = 0;
        for (int i = 1; i < n; i++) {
            // 记录为本次的最小价格
            if (soFarMin > prices[i]) {
                soFarMin = prices[i];
            } else {
                max = Math.max(max, prices[i] - soFarMin);
            }
        }
        return max;
    }

    /**
     * 编写一个程序，找到两个单链表相交的起始节点。
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode l1 = headA;
        ListNode l2 = headB;
        while (l1 != l2) {
            l1 = l1 == null ? headB : l1.next;
            l2 = l2 == null ? headA : l2.next;

        }
        return l1;
    }

    /**
     * 反转一个单链表。
     * <p>
     * 示例:
     * <p>
     * 输入: 1->2->3->4->5->NULL
     * 输出: 5->4->3->2->1->NULL
     *
     * @param head
     * @return
     * @answer 递归
     */
    public ListNode reverseList1(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return head;

        ListNode listNode = reverseList1(head.next);

        head.next.next = head;
        head.next = null;

        return listNode;

    }

    /**
     * 迭代法：存在一个当前指针节点
     *
     * @param head
     * @return
     */
    public ListNode reverseList2(ListNode head) {
        //前指针节点
        ListNode prev = null;
        //当前指针节点
        ListNode curr = head;
        //每次循环，都将当前节点指向它前面的节点，然后当前节点和前节点后移
        while (curr != null) {
            //临时节点，暂存当前节点的下一节点，用于后移
            ListNode nextTemp = curr.next;
            //将当前节点指向它前面的节点
            curr.next = prev;
            //前指针后移
            prev = curr;
            //当前指针后移
            curr = nextTemp;
        }
        return prev;
    }


    ListNode prev = null;

    public ListNode reverseListN(ListNode head, int n) {
        if (n == 1) {
            prev = head.next;
            return head;
        }
        ListNode listNode = reverseListN(head.next, n - 1);
        head.next.next = head;
        head.next = prev;
        return listNode;
    }

    public ListNode reverseListBetween(ListNode head, int m, int n) {
        if (m == 1) {
            return reverseListN(head, n);
        }
        // m<n
        head.next = reverseListBetween(head.next, m - 1, n - 1);
        return head;
    }

    @Test
    public void testReverseListN() {
        ListNode head = new ListNode(1);
        ListNode l2 = new ListNode(2);
        head.next = l2;
        ListNode l3 = new ListNode(3);
        l2.next = l3;
        ListNode l4 = new ListNode(4);
        l3.next = l4;
        ListNode l5 = new ListNode(5);
        l4.next = l5;
        ListNode result = reverseListN(head, 3);
        int val = result.val;
    }

    /**
     * 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
     * <p>
     * 示例：
     * <p>
     * 输入：1->2->4, 1->3->4
     * 输出：1->1->2->3->4->4
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param l1
     * @param l2
     * @return 迭代的方式
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        // 两个指针
        while (l1 != null || l2 != null) {
            int val1 = l1 == null ? Integer.MAX_VALUE : l1.val;
            int val2 = l2 == null ? Integer.MAX_VALUE : l2.val;
            if (val1 < val2) {
                curr.next = l1;
                curr = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                curr = l2;
                l2 = l2.next;
            }
        }
        return dummy.next;
    }

    public ListNode mergeTwoListsP(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (l1 != null || l2 != null) {
            int val1 = l1 == null ? Integer.MAX_VALUE : l1.val;
            int val2 = l2 == null ? Integer.MAX_VALUE : l2.val;
            if (val1 < val2) {
                curr.next = l1;
                curr = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                curr = l2;
                l2 = l2.next;
            }
        }
        return dummy.next;
    }

    public ListNode mergeTwoLists0P(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        int val1 = l1.val;
        int val2 = l2.val;
        if (val1 < val2) {
            l1.next = mergeTwoLists0P(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists0P(l1, l2.next);
            return l2;
        }

    }


    /**
     * 递归的方式，不太懂
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists0(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        if (l1.val <= l2.val) {
            // 如果l1小于l2，那么第一个节点肯定是l1这个当前节点，
            // 然后再比较l1的下一个节点和l2
            l1.next = mergeTwoLists0(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists0(l2.next, l1);
            return l2;
        }
    }

    /**
     * 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
     * <p>
     * 示例 1:
     * <p>
     * 输入: 1->1->2
     * 输出: 1->2
     * 示例 2:
     * <p>
     * 输入: 1->1->2->3->3
     * 输出: 1->2->3
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        head.next = deleteDuplicates(head.next);
        return head.val == head.next.val ? head.next : head;
    }

    @Test
    public void testDeleteDuplicates() {
        ListNode head = new ListNode(1);
        ListNode l2 = new ListNode(1);
        head.next = l2;
        ListNode l3 = new ListNode(2);
        l2.next = l3;
        ListNode l4 = new ListNode(3);
        l3.next = l4;
        ListNode l5 = new ListNode(3);
        l4.next = l5;
        deleteDuplicates(head);


//        if (head == null) {
//            return;
//        }
//        Set<Integer> set = new HashSet<>();
//        ListNode dummy = new ListNode(0);
//        ListNode curr = dummy;
//        while (head != null) {
//            if (set.contains(head.val)) {
//                head = head.next;
//                continue;
//            }
//            set.add(head.val);
//            curr.next = head;
//            curr = head;
//            head = head.next;
//        }
//        return dummy.next;

    }

    /**
     * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
     * <p>
     * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
     * <p>
     * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     * <p>
     * 示例：
     * <p>
     * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
     * 输出：7 -> 0 -> 8
     * 原因：342 + 465 = 807
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/add-two-numbers
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param l1
     * @param l2
     * @return 2->3->5 + 7-> 9  532 + 97 = 629    299 + 91 = 390  54+46= 00
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);

        ListNode cursor = dummy;
        int res = 0;
        // 这样做判断的原因是l1和l2可能不是相等的，并且有进位的情况也需要考虑
        while (l1 != null || l2 != null || res != 0) {
            int l1Val = l1 != null ? l1.val : 0;
            int l2Val = l2 != null ? l2.val : 0;

            int sumVal = l1Val + l2Val + res;
            // 进位
            res = sumVal / 10;
            // 只取余数
            ListNode newNode = new ListNode(sumVal % 10);
            // 构建新的链路
            cursor.next = newNode;
            cursor = newNode;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }


        return dummy.next;
    }


    /**
     * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
     * <p>
     * 示例 1：
     * <p>
     * 输入: "babad"
     * 输出: "bab"
     * 注意: "aba" 也是一个有效答案。
     * 示例 2：
     * <p>
     * 输入: "cbbd"
     * 输出: "bb"
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        // 回文字符串是对称的，怎么判断，反转之后是相等的--双指针

        // 怎么确定子串


        // 中心扩展发法解题
        if (s == null || s.length() < 1) return "";
        // 回文字符串在原串中的定位
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            // 这一步是在以i为中心扩展，找到最大的回文串的长度，对应的回文串的形式为 bcacb
            int len1 = expandAroundCenter(s, i, i);
            // 这一步是在以i和i+1为对称中心，找到最大的回文字符串的长度，对应的示例为：bcaacb
            int len2 = expandAroundCenter(s, i, i + 1);
            // 最大回文串的长度
            int len = Math.max(len1, len2);
            //  大于则要更新
            if (len > end - start) {
                // 该最长回文串在原字符串中的开始位置
                start = i - (len - 1) / 2;
                // 该最长回文串在原字符串中的结束位置
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }


    /**
     * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
     * <p>
     * 示例 1:
     * <p>
     * 输入: "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     * 示例 2:
     * <p>
     * 输入: "bbbbb"
     * 输出: 1
     * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
     * 示例 3:
     * <p>
     * 输入: "pwwkew"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param s
     * @return 解题：此题是基于滑动窗口来解题的，窗口需要一直向右延伸，i为窗口的右边界，left为窗口的左边界；
     * 并且每次延伸（及遍历一次）都需要记录下窗口当前的长度，记为最大值，
     * 对应于代码：max = Math.max(max, i - left + 1);
     * <p>
     * 当延伸的过程中出现相同的字符时，则需要将左边接向前一位。
     * <p>
     * map的作用在于记录各个字符出现的位置，以及判重
     */
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) return 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0;
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            // 在向前遍历的过程中，发现有相同的字符，则窗口的左边界跳到相同字符的前一位，算是开启了一个新的窗口
            // abcae i = 3,left = 0
            if (map.containsKey(s.charAt(i))) {
                left = Math.max(left, map.get(s.charAt(i)) + 1);
            }
            // map的字符，
            map.put(s.charAt(i), i);
            max = Math.max(max, i - left + 1);
        }
        return max;
    }

    /**
     * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
     * <p>
     * 说明：你不能倾斜容器，且 n 的值至少为 2。
     * <p>
     * <p>
     * 示例：
     * <p>
     * 输入：[1,8,6,2,5,4,8,3,7]
     * 输出：49
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/container-with-most-water
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param height
     * @return
     */
    public int maxArea(int[] height) {

        if (height.length == 2) {
            return Math.min(height[0], height[1]);
        }
        return 0;

    }
}
